package com.leetcode.partition7;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/10/24 9:15
 */
public class LC638大礼包 {

    public static int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        List<List<Integer>> filterSpecial = new ArrayList<>();
        //过滤掉不需要计算的大礼包，如大礼包的价格比每个物品单买还贵，就没有必要采用大礼包
        for (List<Integer> sp : special) {
            int totalCount = 0, totalPrice = 0;
            for (int i = 0; i < price.size(); i++) {
                totalCount += sp.get(i);
                totalPrice += sp.get(i) * price.get(i);
            }
            if (totalCount > 0 && totalPrice > sp.get(sp.size() - 1)) {
                filterSpecial.add(sp);
            }
        }
        return memoization(price, needs, filterSpecial, new HashMap<>());
    }

    public static void main(String[] args) {
        List<Integer> price = Arrays.asList(2, 5);
        List<List<Integer>> special = new ArrayList<>();
        special.add(Arrays.asList(3, 0, 5));
        special.add(Arrays.asList(1, 2, 10));
        List<Integer> needs = Arrays.asList(3, 2);
        System.out.println(shoppingOffers(price, special, needs));
    }

    private static int memoization(List<Integer> price, List<Integer> curNeeds, List<List<Integer>> filterSpecial, Map<List<Integer>, Integer> memo) {
        //缓存有数据，直接从缓存中获取
        if (memo.containsKey(curNeeds)) return memo.get(curNeeds);
        int curMinPrice = 0;
        //不购买大礼包，全以单价的形式购买当前所需要的物品
        for (int i = 0; i < curNeeds.size(); i++) curMinPrice += curNeeds.get(i) * price.get(i);

        //尝试购买大礼包，并且要保证购买的数量不能超过所需要的数量
        for (List<Integer> curSpecial : filterSpecial) {
            //购买当前礼包后，下一次递归所需要购买的数量
            List<Integer> nextNeeds = new ArrayList<>();
            boolean outOfCount = false;
            for (int i = 0; i < curSpecial.size() - 1; i++) {
                //如果当前礼包里面内容的数量大于需要的数量，则不选择该礼包
                if (curSpecial.get(i) > curNeeds.get(i)) {
                    outOfCount = true;
                    break;
                }
                nextNeeds.add(curNeeds.get(i) - curSpecial.get(i));
            }
            //超出数量，不采用当前礼包方案
            if (outOfCount) continue;
            //递归计算当前所需要的物品的最小价值，对于每一个大礼包，都有两种情况，要么选择，要么不选择
            curMinPrice = Math.min(curMinPrice, memoization(price, nextNeeds, filterSpecial, memo) + curSpecial.get(curSpecial.size() - 1));
        }
        memo.put(curNeeds, curMinPrice);
        return curMinPrice;
    }
}
